Search for: All records

Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Several recent articles have studied the algorithmic and complexity aspects of some decision problems on synchronous Boolean networks, which are discrete dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. Previous work has shown that some of these decision problems become efficiently solvable for systems on directed acyclic graphs (DAGs). Motivated by this line of work, we investigate a number of decision problems for dynamical systems whose underlying graphs are DAGs. We show that computational intractability (i.e.,PSPACE-completeness) results for reachability problems hold even for dynamical systems on DAGs. We also identify some restricted versions of dynamical systems on DAGs for which reachability problem can be solved efficiently. In addition, we show that a decision problem (namely, Convergence), which is efficiently solvable for dynamical systems on DAGs, becomesPSPACE-complete for Quasi-DAGs (i.e., graphs that become DAGs by the removal of asingleedge). In the process of establishing the above results, we also develop several structural properties of the phase spaces of dynamical systems on DAGs. 

Networks allow us to describe a wide range of interaction phenomena that occur in complex systems arising in such diverse fields of knowledge as neuroscience, engineering, ecology, finance, and social sciences. Until very recently, the primary focus of network models and tools has been on describing the pairwise relationships between system entities. However, increasingly more studies indicate that polyadic or higher-order group relationships among multiple network entities may be the key toward better understanding of the intrinsic mechanisms behind the functionality of complex systems. Such group interactions can be, in turn, described in a holistic manner by simplicial complexes of graphs. Inspired by these recently emerging results on the utility of the simplicial geometry of complex networks for contagion propagation and armed with a large-scale synthetic social contact network (also known as a digital twin) of the population in the U.S. state of Virginia, in this paper, we aim to glean insights into the role of higher-order social interactions and the associated varying social group determinants on COVID-19 propagation and mitigation measures. 

Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to certain classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems. 

The SARS-CoV-2 pandemic has generated a considerable number of infections and associated morbidity and mortality across the world. Recovery from these infections, combined with the onset of large-scale vaccination, have led to rapidly-changing population-level immunological landscapes. In turn, these complexities have highlighted a number of important unknowns related to the breadth and strength of immunity following recovery or vaccination. Using simple mathematical models, we investigate the medium-term impacts of waning immunity against severe disease on immuno-epidemiological dynamics. We find that uncertainties in the duration of severity-blocking immunity (imparted by either infection or vaccination) can lead to a large range of medium-term population-level outcomes (i.e. infection characteristics and immune landscapes). Furthermore, we show that epidemiological dynamics are sensitive to the strength and duration of underlying host immune responses; this implies that determining infection levels from hospitalizations requires accurate estimates of these immune parameters. More durable vaccines both reduce these uncertainties and alleviate the burden of SARS-CoV-2 in pessimistic outcomes. However, heterogeneity in vaccine uptake drastically changes immune landscapes toward larger fractions of individuals with waned severity-blocking immunity. In particular, if hesitancy is substantial, more robust vaccines have almost no effects on population-level immuno-epidemiology, even if vaccination rates are compensatorily high among vaccine-adopters. This pessimistic scenario for vaccination heterogeneity arises because those few individuals that are vaccine-adopters are so readily re-vaccinated that the duration of vaccinal immunity has no appreciable consequences on their immune status. Furthermore, we find that this effect is heightened if vaccine-hesitants have increased transmissibility (e.g. due to riskier behavior). Overall, our results illustrate the necessity to characterize both transmission-blocking and severity-blocking immune time scales. Our findings also underline the importance of developing robust next-generation vaccines with equitable mass vaccine deployment.